Neat Tree

题目链接： https://ac.nowcoder.com/acm/problem/15815?&headNav=acm

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF=0x3f3f3f3f;
const int MAX_N=1e6+5;
const int mod=100003;
int n;
int a[MAX_N];
stack<int> sta;
int l[MAX_N];
int r[MAX_N];
int main(){

    while(scanf("%d",&n)!=EOF)
    {
        ll ans=0;
        for(int i=1;i<=n;i++)
        {
            scanf("%d",a+i);
        }
        for(int i=1;i<=n;i++)
        {
            while(sta.size()&&a[sta.top()]>a[i]) sta.pop();             //注意这里的">"号不是>=
            l[i]=sta.empty()?1:sta.top()+1;
            sta.push(i);
        }
        while(sta.size()) sta.pop();
        for(int i=n;i>=1;i--)
        {
            while(sta.size()&&a[sta.top()]>=a[i]) sta.pop();            //这里是">="，避免前后两个区间重合。
            r[i]=sta.empty()?n:sta.top()-1;
            sta.push(i);
        }
        while(sta.size()) sta.pop();
        for(int i=1;i<=n;i++)
        {
            ans-=(ll)a[i]*((ll)(r[i]-i+1)*(ll)(i-l[i]+1)-1);        //一个[a,b]区间里的集合为b-a+1,1是指为空的时候。
        }
        for(int i=1;i<=n;i++)
        {
            while(sta.size()&&a[sta.top()]<a[i]) sta.pop();
            l[i]=sta.empty()?1:sta.top()+1;
            sta.push(i);
        }
        while(sta.size()) sta.pop();
        for(int i=n;i>=1;i--)
        {
            while(sta.size()&&a[sta.top()]<=a[i]) sta.pop();
            r[i]=sta.empty()?n:sta.top()-1;
            sta.push(i);
        }
        while(sta.size()) sta.pop();
        for(int i=1;i<=n;i++)
        {
            ans+=(ll)a[i]*((ll)(r[i]-i+1)*(ll)(i-l[i]+1)-1);
        }
        printf("%lld\n",ans);
    }

    return 0;
}

其实可以两次循环就做完了，一次循环就能求出L和R。进栈的时候可以求出L[i]，出栈的时候可以求出sta.top的R;